/*
 * Created by SharpDevelop.
 * User: daniel
 * Date: 12/25/2006
 * Time: 9:46 PM
 * 
 * To change this template use Tools | Options | Coding | Edit Standard Headers.
 */

using System;
using System.Collections;

namespace MonoDoku
{
	/// <summary>
	/// Description of Solver.
	/// </summary>
	public class Solver
	{
		
		private Board board;
		
		public Solver()
		{
		}
		
		public Board solve( Board board ){
			this.board = board;
			bool progress_made = true;
			while( ! board.solved() ){
				Stack open_spaces = board.free_spaces();
				
				if( progress_made == true ){
					progress_made = false;
					while( open_spaces.Count != 0 )
					{
						Coords c = (Coords) open_spaces.Pop();
						int i  = try_place( c );
						
						//If 2 is returned, the board cannot be solved because
						//This space has no possible moves. Return null.
						if( i == 2 ){
							return null;
						}
						if( i == 1 ) progress_made = true;
					}
				}
				else{
					return branching_try();
				}
			}
			
			return board;
		}
		
		//Returns 1 if the place is solved
		//Returns 0 if the place is not solved
		//Returns 2 if the place cannot be solved
		private int try_place( Coords c ){
			int size = board.group_size();
			PossibilitySet poss = new PossibilitySet( size );
			
			poss = do_eliminations( c, poss );
			

			if( poss.is_single() ){
				this.board.set_place( c, poss.get_single() );
				return 1;
			}
			else if( poss.has_none() ){
				return 2;
			}
			else return 0;
		}
		
		private Board branching_try(){
			Stack spaces = board.free_spaces();
			
			Coords c = (Coords) spaces.Pop();
			
			PossibilitySet p = do_eliminations( c, new PossibilitySet( board.group_size() ) );
			
			foreach( int i in p.all_possibilities() ){
				Solver s = new Solver();
				Board b = board.copy();
				b.set_place( c, i );
				b = s.solve( b );
				if ( b != null ) return b;
			}
			
			return null;
		}
		
		private PossibilitySet do_eliminations( Coords c, PossibilitySet poss ){
			int[] row = board.get_col( c );
			int[] col = board.get_row( c );
			int[] grp = board.get_grp( c );
			
			foreach( int i in row ){
				if( i != 0) poss.remove_possibility( i );
			}
			foreach( int i in col ){
				if( i != 0) poss.remove_possibility( i );
			}
			foreach( int i in grp ){
				if( i != 0) poss.remove_possibility( i );
			}
			
			return poss;
		}
		
		
	}
}
